1. Field of the Invention
The present invention generally relates to incrementally maintaining algebraic functions in automatic summary tables (ASTs) of at least one relational database.
2. Description of the Related Art
Within this application several publications are referenced by Arabic numerals within parentheses. Full citations for these, and other, publications may be found at the end of the specification immediately preceding the claims. The disclosures of all these publications in their entireties are hereby expressly incorporated by reference into the present application for the purposes of indicating the background of the present invention and illustrating the state of the art.
Automatic Summary Tables (ASTs), which are also known as materialized views physically, store derived data from several relational database tables. ASTs are of important usage to various applications to improve query performance [3] such as OLAP or data mining applications. However, as base tables change over time, one of the important issues of ASTs is to maintain the ASTs extent upon base changes. Since re-computation from base tables is usually expensive, incremental maintenance of ASTs is often a better solution in terms of performance [1, 6, 7].
Materialized views, or Automatic Summary Tables (ASTs), are increasingly being used to facilitate the analysis of the large amounts of data being collected in relational databases. The use of ASTs can significantly reduce the execution time of a query. This reduction in execution time is particularly significant for databases with sizes in the terabyte to petabyte range. Such queries tend to be extremely complex and can involve a large number of join and grouping operations.
One major advantage of using ASTs is that they are precomputed once and subsequently can be used multiple times to quickly answer complex queries. When base is relations are modified, these modifications must be propagated to the affected ASTs. Unfortunately, using current techniques, the systems can only incrementally update a restricted set of ASTs, e.g., those only containing distributive aggregate functions. The remainder must be fully recomputed. Previous work has studied the problem of incremental view maintenance in which all the necessary changes for the AST are computed based only on the modifications to the base table (and the corresponding values in the AST). This process is called incremental view maintenance and many commercial products support it.
Due to the complexity of the queries and the magnitude of the data, recomputation of ASTs in large-scale databases is prohibitive. Since the set of updates to the base tables is usually only some small percentage of those tables, incremental maintenance of an AST is usually much quicker than full recomputation. For example, a typical warehouse may contain up to six (6) years of data. Daily inserts into a fact table in this warehouse may constitute only about five hundredths of a percent (0.05%) of the entire size of the table. When updates occur in the base data, the system determines which ASTs are affected and propagates the changes through the AST definitions to produce the delta changes. It then applies these deltas to their respective ASTs. If an AST is automatically refreshed in the same unit of work as the changes to the underlying base data are applied, then the maintenance is considered immediate. Otherwise, it is deferred.